Наивный байесовский классификатор
Наи́вный ба́йесовский классифика́тор — простой вероятностный классификатор, основанный на применении Теоремы Байеса со строгими (наивными) предположениями о независимости. В зависимости от точной природы вероятностной модели, наивные байесовские классификаторы могут обучаться очень эффективно. Во многих практических приложениях, для оценки параметров для наивных байесовых моделей используют метод максимального правдоподобия; другими словами, можно работать с наивной байесовской моделью, не веря в байесовскую вероятность и не используя байесовские методы. Несмотря на наивный вид и, несомненно, очень упрощенные условия, наивные байесовские классификаторы часто работают намного лучше во многих сложных жизненных ситуациях. Достоинством наивного байесовского классификатора является малое количество данных для обучения, необходимых для оценки параметров, требуемых для классификации. Модель наивного байесовского классификатора Абстрактно, вероятностная модель для классификатора — это условная модель : p(C \vert F_1,\dots,F_n)\, над зависимой переменной класса C с малым количеством результатов или классов, зависимая от нескольких переменных F_1 … F_n . Проблема заключается в том, что когда количество свойств n очень велико или когда свойство может принимать большое количество значений, тогда строить такую модель на вероятностных таблицах становится невозможно. Поэтому мы переформулируем модель, чтобы сделать ее легко поддающейся обработке. Используя теорему Байеса, запишем : p(C \vert F_1,\dots,F_n) = \frac{p© \ p(F_1,\dots,F_n\vert C)}{p(F_1,\dots,F_n)}. \, На практике мы заинтересованы лишь в числителе этой дроби, так как знаменатель не зависит от C и значения свойств F_i даны, так что знаменатель — константа. Числитель эквивалентен совместной вероятности модели : p(C, F_1, \dots, F_n)\, которая может быть переписана следующим образом, используя повторные приложения определений условной вероятности: : p(C, F_1, \dots, F_n)\, :: = p© \ p(F_1,\dots,F_n\vert C) :: = p© \ p(F_1\vert C) \ p(F_2,\dots,F_n\vert C, F_1) :: = p© \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3,\dots,F_n\vert C, F_1, F_2) :: = p© \ p(F_1\vert C) \ p(F_2\vert C, F_1) \ p(F_3\vert C, F_1, F_2) \ p(F_4,\dots,F_n\vert C, F_1, F_2, F_3) и т. д. Теперь начинаем использовать «наивные» предположения условной независимости: предположим, что каждое свойство F_i условно независимо от любого другого свойства F_j при j\neq i . Это означает : p(F_i \vert C, F_j) = p(F_i \vert C)\, таким образом, совместная модель может быть выражена как : p(C, F_1, \dots, F_n) = p© \ p(F_1\vert C) \ p(F_2\vert C) \ p(F_3\vert C) \ \cdots\, : = p© \prod_{i=1}^n p(F_i \vert C).\, Это означает, что из предположения о независимости, условное распределение по классовой переменной C может быть выражено так: : p(C \vert F_1,\dots,F_n) = \frac{1}{Z} p© \prod_{i=1}^n p(F_i \vert C) где Z — это масштабный множитель, зависящий только от F_1,\dots,F_n , то есть константа, если значения переменных известны. Оценка параметров Все параметры модели могут быть аппроксимированы относительными частотами из набора данных обучения. Это оценки максимального правдоподобия вероятностей. Не дискретные свойства должны быть сначала дискретизированы. Если данный класс и значений свойства никогда не встречаются вместе в наборе обучения, тогда оценка, основанная на вероятностях, будет равна нулю. Это проблема, так как при перемножении нулевая оценка приведет к потере информации о других вероятностях. Поэтому предпочтительно проводить небольшие поправки во все оценки вероятностей так, чтобы никакая вероятность не была строго равна нулю. Построение классификатора по вероятностной модели Наивный байесовский классификатор объединяет модель с правилом решения. Одно общее правило должно выбрать наиболее вероятную гипотезу; оно известно как апостериорное правило принятия решения (MAP). Соответствующий классификатор — это функция \mathrm{classify}, определённая следующим образом: : \mathrm{classify}(f_1,\dots,f_n) = \mathop{\mathrm{argmax}}_c \ P(C=c) \prod_{i=1}^n p(F_i=f_i\vert C=c) Пример: классификация документов Рассморим пример применения наивной байесовской классификации к задаче классификации документов. Рассмотрим задачу классификации документов по их содержимому, например в спам и не-спам E-Mail. Будем считать, что документы выбраны из нескольких классов документов, которые могут быть представлены множеством слов с (независимой) вероятностью, что i''-ое слово данного документа встречается в документе класса ''C: : p(w_i \vert C)\, (Для этой задачи предположим, что вероятность встречи слова в документе независима от длины документа и все документы имеют одинаковую длину.) Тогда вероятность для данного документа D'' и класса ''C : p(D\vert C)=\prod_i p(w_i \vert C)\, Вопрос, на который мы хотим ответить: «какова вероятность того, что данный документ D'' принадлежит классу ''C?» Другими словами, чему равна p(C \vert D)\, ? По определению, (см. Аксиома вероятности) : p(D\vert C)={p(D\cap C)\over p©} и : p(C\vert D)={p(D\cap C)\over p(D)} Байесовская теорема манипулирует этим в терминах подобия. : p(C\vert D)={p©\over p(D)}\,p(D\vert C) Предположим, что мы имеем только два класса: S'' и ¬''S (напр. спам и не-спам). : p(D\vert S)=\prod_i p(w_i \vert S)\, и : p(D\vert\neg S)=\prod_i p(w_i\vert\neg S)\, Используя байесовский результат выше, мы можем написать: : p(S\vert D)={p(S)\over p(D)}\,\prod_i p(w_i \vert S) : p(\neg S\vert D)={p(\neg S)\over p(D)}\,\prod_i p(w_i \vert\neg S) Разделив один на другой, будем иметь: : {p(S\vert D)\over p(\neg S\vert D)}={p(S)\,\prod_i p(w_i \vert S)\over p(\neg S)\,\prod_i p(w_i \vert\neg S)} Можно переписать как: : {p(S\vert D)\over p(\neg S\vert D)}={p(S)\over p(\neg S)}\,\prod_i {p(w_i \vert S)\over p(w_i \vert\neg S)} Итак, вероятность p(S'' | ''D) / p(¬''S'' | D'') может быть выражена в терминах последовательности степени правдопобия. Действительная вероятность p(''S | D'') может быть просто посчитана из ln(p(''S | D'') / p(¬''S | D'')) основываясь на наблюдении, что p(''S | D'') + p(¬''S | D'') = 1. Взяв логарифм всех этих степеней, имеем: : \ln{p(S\vert D)\over p(\neg S\vert D)}=\ln{p(S)\over p(\neg S)}+\sum_i \ln{p(w_i\vert S)\over p(w_i\vert\neg S)} (Этот метод «степеней логарифмического правдопобия» — часто встречающийся метод в статистике.) Наконец, документ может быть классифицирован следующим образом. Это спам, если \ln{p(S\vert D)\over p(\neg S\vert D)} > 0 , иначе это не спам. См. также * Байесовская сеть доверия * Линейный классификатор * Нечеткая логика * Нейронные сети Ссылки * Domingos, Pedro & Michael Pazzani (1997) «On the optimality of the simple Bayesian classifier under zero-one loss». ''Machine Learning, 29:103-137. (also online at CiteSeer: http://citeseer.ist.psu.edu/domingos97optimality.html) * Rish, Irina. (2001). «An empirical study of the naive Bayes classifier». IJCAI 2001 Workshop on Empirical Methods in Artificial Intelligence. (available online: PDF, PostScript) * Hand, DJ, & Yu, K. (2001). «Idiot’s Bayes — not so stupid after all?» International Statistical Review. Vol 69 part 3, pages 385—399. . * Mozina M, Demsar J, Kattan M, & Zupan B. (2004). «Nomograms for Visualization of Naive Bayesian Classifier». In Proc. of PKDD-2004, pages 337—348. (available online: PDF) * Maron, M. E. (1961). «Automatic Indexing: An Experimental Inquiry.» Journal of the ACM (JACM) 8(3):404-417. (available online: PDF) * Minsky, M. (1961). «Steps toward Artificial Intelligence.» Proceedings of the IRE 49(1):8-30. * McCallum, A. and Nigam K. «A Comparison of Event Models for Naive Bayes Text Classification». In AAAI/ICML-98 Workshop on Learning for Text Categorization, pp. 41-48. Technical Report WS-98-05. AAAI Press. 1998. (available online: PDF) ;Программные продукты * Naive Bayes implementation in Visual Basic (includes executable and source code). * jBNC - Bayesian Network Classifier Toolbox Категория:Машинное обучение Категория:Алгоритмы классификации Категория:Байесовская статистика